package src.com.java.dtgh.twoDay;

import src.com.java.Util;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class demo3 {


    public boolean canPartition(int[] nums){

        int target = 0;

        for (int num : nums) {
            target += num;
        }

        if(target % 2 != 0){
            return false;
        }
        target = target / 2;

        int[] dp = new int[target + 1];
        Arrays.fill(dp, 0);

        int len = nums.length;

        for(int i = 0;i < len;i++){
            for(int j = target;j >= nums[i];j--){
                dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }

        return dp[target] == target;
    }

    public static void main(String[] args) {
        demo3 demo3 = new demo3();
        demo3.canPartition2(new int[]{1,5,11,5});
    }

    public boolean canPartition2(int[] nums){


        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0){
            return false;
        }
        int target = sum / 2;
        int[][] dp = new int[nums.length][target + 1];

        for(int i = 0;i < nums.length;i++){
            dp[i][0] = 0;
        }

        for(int j = 0;j <= target;j++){

            if(j >= nums[0]){
                dp[0][j] = nums[0];
            }
        }

        for(int i = 1;i < nums.length;i++){
            for(int j = 1;j <= target;j++){

                if(j < nums[i]){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i]);
                }
            }
        }
        Util.printArray2(dp);
        return dp[nums.length-1][target] == target;
    }

}
